#include <vector>

using namespace std;

class Solution {
public:
    // 174. 地下城游戏
    // https://leetcode.cn/problems/dungeon-game/
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();   
        int n = dungeon[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));

        dp[m][n-1] = 1, dp[m-1][n] = 1;

        for (int i = m-1; i>=0; --i)
        {
            for (int j = n-1; j>=0; --j)
            {
                dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }

        return dp[0][0];
    }

    // 面试题 17.16. 按摩师
    // https://leetcode.cn/problems/the-masseuse-lcci/
    int massage(vector<int>& nums) {
        if (nums.size() < 1)
        {
            return 0;
        }
        int n = nums.size();
        vector<int> f(n), g(n);

        f[0] = nums[0];
        g[0] = 0;

        for (int i = 1; i<n; ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }

        return max(f[n-1], g[n-1]);
    }

    // 198. 打家劫舍
    // https://leetcode.cn/problems/house-robber/
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        vector<int> f(n), g(n);
        f[0] = nums[0];

        for (int i = 1; i<n; ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }

        return max(f[n-1], g[n-1]);
    }

    // 213. 打家劫舍 II
    // https://leetcode.cn/problems/house-robber-ii/
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        return max(nums[0] + rob1(nums, 2, n-2), rob1(nums, 1, n-1));
    }

    int rob1(vector<int>& nums, int left, int right)
    {
        if (left > right) return 0;

        int n = nums.size();
        vector<int> f(n), g(n);
        f[left] = nums[left];

        for (int i = left + 1; i<=right; ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }

        return max(f[right], g[right]);
    }

    // 740. 删除并获得点数
    // https://leetcode.cn/problems/delete-and-earn/
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 0) return 0;

        vector<int> f(n), g(n);
        f[0] = nums[0];

        for (int i = 1; i<n; ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }

        return max(f[n-1], g[n-1]);
    }

    int deleteAndEarn(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int maxVal = *max_element(nums.begin(), nums.end());
        
        vector<int> hash(maxVal+1);
        for (int num : nums)
            hash[num] += num;

        return rob(hash);
    }
};